package Algorithm.RecursionAndRecurrence;

import java.util.Scanner;


/**  100 可以表示为带分数的形式：100=3+69258/714, 还可以表示为：100=82+3546/197
 注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0 ）。
 类似这样的带分数，100 有 11 种表示法。
 输入格式:
 一个正整数。
 输出格式 :
 输出输入数字用数码 1∼9
 不重复不遗漏地组成带分数表示的全部种数。

 数据范围
 1≤N<106

 输入样例1：
 100
 输出样例1：
 11
 输入样例2：
 105
 输出样例2：
 6
 */


public class RecursionPractical {
    private int N;
    private int totalCount;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        new RecursionPractical().solve(n);
    }

    public void solve(int n) {
        N = n;
        totalCount = 0;
        int[] current = new int[9]; // 存储当前排列
        boolean[] used = new boolean[10]; // 标记数字是否使用过（索引0不用）
        generatePermutations(current, used, 0);
        System.out.println(totalCount);
    }

    /**
     * 生成1-9的全排列
     * @param current 当前排列数组
     * @param used 标记数字是否使用过
     * @param depth 当前递归深度（已生成的排列长度）
     */
    private void generatePermutations(int[] current, boolean[] used, int depth) {
        if (depth == 9) { // 排列完成，处理
            processPermutation(current);
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (!used[i]) {
                used[i] = true;
                current[depth] = i;
                generatePermutations(current, used, depth + 1);


                used[i] = false; // 回溯
            }
        }
    }

    /**
     * 处理一个完整的排列，枚举分割点并验证条件
     * @param perm 完整的排列数组
     */
    private void processPermutation(int[] perm) {
        // 枚举A的长度i（1到7，保证B和C至少各1位）
        for (int i = 1; i <= 7; i++) {
            int A = toInt(perm, 0, i);
            if (A >= N) { // A必须小于N，否则B/C无法为正整数
                continue;
            }
            // 枚举B的结束位置j（i+1到8，保证C至少1位）
            for (int j = i + 1; j <= 8; j++) {
                int B = toInt(perm, i, j);
                int C = toInt(perm, j, 9);
                if (C == 0) { // 数字都是1-9，C不可能为0
                    continue;
                }
                if (B % C != 0) { // B必须能被C整除
                    continue;
                }
                if (A + B / C == N) { // 满足带分数条件
                    totalCount++;
                }
            }
        }
    }

    /**
     * 将排列的某段转换为整数
     * @param perm 排列数组
     * @param start 起始索引（包含）
     * @param end 结束索引（不包含）
     * @return 转换后的整数
     */
    private int toInt(int[] perm, int start, int end) {
        int res = 0;
        for (int k = start; k < end; k++) {
            res = res * 10 + perm[k];
        }
        return res;
    }
}
